#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/23 23:15
# @Author  : Yuyun
# @File    : leetcode_503_下一个更大元素II.py
# @IDE     : PyCharm


"""
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:
1 <= nums.length <= 10^4
-109 <= nums[i] <= 10^9
"""

class Solution:
    #   扩充数组，将两个数组拼接在一起，再使用单调栈求最大值
    def next_bigger_number_in_loop(self, nums):
        nums_test = nums + nums
        length_test = len(nums_test)
        length = len(nums)
        #   记录下标
        stack = []
        #   记录结果
        result = [-1] *  length
        #   将各个下标压入栈
        for i in range(length_test):
            #   栈不为空 且 当前数组数值 > 栈顶下标对应数组数值
            while stack and nums_test[i] > nums_test[stack[-1]]:
                #   计算栈顶下标的结果 = 当前下标值 - 栈顶下标值
                #   如果超出 nums数组长度，则减去长度
                if i >= length:
                    result[stack[-1] - length] = nums_test[i]
                else:
                    result[stack[-1]] = nums_test[i]
                #   推出栈顶下标值
                stack.pop()
            #   其他情况，下标压栈
            stack.append(i)
        return result
    #   遍历两遍数组（不扩充数组）
    def next_bigger_number_in_loop(self, nums):
        length = len(nums)
        #   记录下标
        stack = []
        #   记录结果
        result = [-1] *  length
        #   将各个下标压入栈，将遍历次数扩大至2倍
        for i in range(length * 2):
            #   栈不为空 且 当前数组数值 > 栈顶下标对应数组数值
            while stack and nums[i % length] > nums[stack[-1]]:
                #   计算栈顶下标的结果 = 当前下标值 - 栈顶下标值
                result[stack[-1]] = nums[i % length]
                #   推出栈顶下标值
                stack.pop()
            #   其他情况，下标i % length压栈，栈长度仍然等于数组长度
            stack.append(i % length)
        return result

if __name__ == '__main__':
    nums = list(map(int, input().split(',')))
    solution = Solution()
    result = solution.next_bigger_number_in_loop(nums)
    print(result)
